package com.algorithm;

/**
 * 打家劫舍(动态规划)
 */
public class HouseRobber {

    public static int rob(int[] nums) {
//        if (nums.length==0){
//            return 0;
//        }
//        if (nums.length==1){
//            return nums[0];
//        }
//        int temp[]= new int[nums.length];
//        temp[0]=nums[0];
//        temp[1]=Math.max(nums[0],nums[1]);
//        for (int i=2;i<nums.length;i++){
//            temp[i]=Math.max(nums[i]+temp[i-2],temp[i-1]);
//        }
//        return temp[nums.length-1];

        if (nums.length==0){
            return 0;
        }
        if (nums.length==1){
            return nums[0];
        }
        int temp2;
        int temp1;
        int temp;
        temp2=nums[0];
        temp1=Math.max(nums[0],nums[1]);
        for (int i=2;i<nums.length;i++){
            temp=Math.max(nums[i]+temp2,temp1);
            temp2=temp1;
            temp1=temp;
        }
        return temp1;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 1};
        int rob = rob(nums);
        System.out.println(rob);
    }
}
